package com.wang.utils.query;

/**
 * @author 10570
 * @date 2021/8/2 0:29
 */


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 线形查找
 */
public class SeqSearch {
    public static void main(String[] args) {

        //二分为有序数组
        int[] ints =new int[6];
        for (int i = 0; i < 6; i++){
            ints[i] = i + 1;
            //            ints[i] = (int)(Math.random() * 10);
            System.out.println(ints[i]);
        }


//        List list = binarySearchAll(ints, 0, ints.length-1, 4);
//        int index = insertValue(ints, 0, ints.length-1, 4);
//        int index1 = binarySearch(ints, 0, ints.length-1, 20);
//        System.out.println("数组下标index = "+ index1);
//        //斐波那契数列
        int n = fibonacciSearch(ints,6);
        System.out.println(n);



    }


    //线性查找
    public static int seqSearch(int[] arr,int value ){
        for (int i = 0;i<arr.length;i++){
            if (arr[i] == value){
                return i;
            }
        }
        return -1;
    }

    /**
     * 二分查找：必须为有序数组
     *  1、确定中间位置的下标  mid = （left+right）/2
     *  2、需要查找的数和中间数比较
     *      大于  --》 就继续mid向右查找的数据二分查找   递归查找
     *      小于  --》 就继续mid向左查找
     *      等于  --》 返回
     *  3、递归停止的条件
     *      1）查找到值
     *      2）递归到left > right 停止递归
     */
    public static int binarySearch(int[] arr,int left,int right,int value){
        System.out.println("二分查找数组次数");
        int mid = (left + right)/2;
        int midVal = arr[mid];
        if (left > right){
            return -1;
        }
        if (midVal < value){
            return binarySearch(arr,mid + 1,right,value);
        }else if (midVal > value){
            return binarySearch(arr,left,mid-1,value);
        }else {
            return mid;
        }

    }

    /**
     * 找到mid值时，不返回 (变体，找到所有符合的值)
     * 1、向mid的左侧扫描，找到所有的满足值，加入一个数组
     * 2、向mid的右边扫描，找到所有的满足值，加入一个数组
     * @param arr
     * @param left
     * @param right
     * @param value
     * @return
     */
    public static List binarySearchAll(int[] arr, int left, int right, int value){
        List  list = new ArrayList();
        int mid = (left + right)/2;
        int midVal = arr[mid];
        if (left > right){
            return list;
        }
        if (midVal > value){
            return binarySearchAll(arr,left,mid-1,value);
        }else if (midVal < value){
            return binarySearchAll(arr,mid + 1,right,value);
        }else {
            int temp = mid-1;
            //1、向mid的左侧扫描，找到所有的满足值，加入一个数组
            while (true){
                if (temp < 0 || arr[temp] != value){
                    break;
                }
                list.add(temp);
                temp -= 1;
            }
            list.add(mid);
            //向mid的右边扫描，找到所有的满足值，加入一个数组
            int temp2 = mid + 1;
            while (true){
                if (temp2 > arr.length -1 || arr[temp2] != value){
                    break;
                }
                list.add(temp2);
                temp2 += 1;
            }
            return list;
        }

    }

    /**
     * 插值查找要求数组有序
     *
     * @param arr
     * @param low  最左
     * @param high  最右
     * @param finalVal  查找值
     * @return 返回位置
     */
    //自适应的写法--减少查找次数
    //数据量较大，关键字分布比较均匀
    //分布不均匀时，不一定优于二分查找
    public static int insertValue(int[] arr,int low ,int high,int finalVal){
        System.out.println("查找次数");
        //找到返回对应值，找不到返回-1【防止数组越界】
        if (low > high || finalVal < arr[0] || finalVal > arr[arr.length-1]){
            return -1;
        }
        //找出mid
        int mid = low + (high - low ) * ( finalVal - arr[low])/(arr[high] - arr[low]);
        int midVal = arr[mid];

        //要向右查找
        if (finalVal > midVal){
            return insertValue(arr,mid+1,high,finalVal);
        }else if (finalVal < midVal){
            return insertValue(arr,low,mid-1,finalVal);
        }else {
            return mid;
        }
    }

    /**
     * 非递归的方式
     * 意义在什么地方，什么情况下会应用
     * @param a 斐波那契数列
     * @param key 关键字
     * @return 对应下标
     */
    public static int fibonacciSearch(int[] a,int key){
        //int mid = low + F(k-1)-1
        int low = 0;
        int high = a.length -1;
        int k = 0; //斐波那契数列分割值对应的下标
        int mid = 0;
        int[] f = fib(); //获取到斐波那契数列
        //获取k  下标
        while (high> f[k]-1){
            k++;
        }
        //f[k] 的值，可能大于数组的长度，使用一个array类，构造一个新的数组，指向a
        //使用a数组最后的值，填充temp数组
        int[] temp = Arrays.copyOf(a,f[k]);
        for (int i = high+1; i<temp.length; i++){
            temp[i] = a[high];
        }
        //循环处理找到key
        //条件满足就可以一直找
        while (low < high){
            mid = low + f[k-1]-1;
            if (key < temp[mid]){
                //说明要向数组的前面继续查找
                high = mid-1;
                //k--的意思
                //(f[k]-1)=f[k-1]-1 +( f[k-2]-1)+1
                //全部原属= 前面的元素 + 后面元素
                // f(k) = f(k-1) + f(k-2)
                //前面有k-1 个元素，因此可以继续拆分
                //(F[k]-1) = (F[k-1]-1) + (F[k-2]-1) - 1
                //f(k-1) = f((k-1)-1) + f((k-1)-2) ,f(k-1)的前面继续查找  使用 k--
                //mid = f[k-1-1] - 1
                k--;
            }else if (key > temp[mid]){
                low = mid +1;
                //为什么 k-2
                //1、全部元素= 前面的元素 + 后面元素
                //2、 f(k) = f(k-1) + f(k-2)
                //3、后面有 f(k-2) 个元素  f(k-1) = f((k-2)-1) + f((k-2)-2)  => 对于k来说， k 表示 k-2
                //4、在f(k-2) 继续查找
                //mid = f[k-1-2] - 1
                //确定返回的是哪个下标
                // TODO: 2021/8/7 待解释
                 k -= 2;
            }else {
                if (mid <= high){
                    return mid;
                }else {
                    return high;
                }
            }
        }
        return -1;

    }
    static  int maxSize = 20;
    public static int[] fib(){
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize;i++){
            f[i] = f[i-1]+f[i-2];
         }
        return f;
    }

}
